/**
 * Universidad del Valle de Guatemala
 * Algoritmos y estructura de datos
 * @author Julio R. Chicas Sett
 * Carne: 07470
 * Programa: MAIN
 * Descripcion: MAIN
 */


import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;


public class Cosa
{
    public static void prueba(Vertice fuente)
    {
        fuente.minDistance = 0.;
        PriorityQueue<Vertice> verticeQueue = new PriorityQueue<Vertice>();
        verticeQueue.add(fuente);

        while (!verticeQueue.isEmpty()) {
            Vertice u = verticeQueue.poll();

            // Visit each edge exiting u
            for (Nodo e : u.adjacencies)
            {
                Vertice v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    verticeQueue.remove(v);

                    v.minDistance = distanceThroughU ;
                    v.previous = u;
                    verticeQueue.add(v);

                }

            }
        }
    }


    public static List<Vertice> prueba2(Vertice target)
    {
        List<Vertice> path = new ArrayList<Vertice>();
        for (Vertice vertice = target; vertice != null; vertice = vertice.previous)
            path.add(vertice);

        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        Vertice lado0 = new Vertice("Guatemala");
        Vertice lado1 = new Vertice("Chiquimula");
        Vertice lado2 = new Vertice("Quiche");
        Vertice lado3 = new Vertice("Solola");
        Vertice lado4 = new Vertice("Peten");
        Vertice lado5 = new Vertice("Zacapa");
        Vertice lado6 = new Vertice("Xela");

        lado0.adjacencies = new Nodo[]{ new Nodo(lado1,  79.83),
                                     new Nodo(lado5,  81.15) };
        lado1.adjacencies = new Nodo[]{ new Nodo(lado0,  79.75),
                                     new Nodo(lado2,  39.42),
                                     new Nodo(lado3, 103.00) };
        lado2.adjacencies = new Nodo[]{ new Nodo(lado1,  38.65) };
        lado3.adjacencies = new Nodo[]{ new Nodo(lado1, 102.53),
                                     new Nodo(lado5,  61.44),
                                     new Nodo(lado6,  96.79) };
        lado4.adjacencies = new Nodo[]{ new Nodo(lado5, 133.04) };
        lado5.adjacencies = new Nodo[]{ new Nodo(lado0,  81.77),
                                     new Nodo(lado3,  62.05),
                                     new Nodo(lado4, 134.47),
                                     new Nodo(lado6,  91.63) };
        lado6.adjacencies = new Nodo[]{ new Nodo(lado3,  97.24),
                                     new Nodo(lado5,  87.94) };
        Vertice[] vertices = { lado0, lado1, lado2, lado3, lado4, lado5, lado6 };


        prueba(lado0);
        for (Vertice v : vertices)
        {
            System.out.println("Distancia a : " + v + ": " + v.minDistance);
            List<Vertice> path = prueba2(v);
            System.out.println("Fuente: " + path);
        }

    }
}